package com.dyz.leetcode._07_hashSearch;

import java.util.HashSet;
import java.util.Set;

public class _41_firstMissingPositive {
    public int firstMissingPositive1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {set.add(num);}
        for (int i = 1; i <= nums.length; i++) {
            // 哈希查找
            if (!set.contains(i)) {return i;}
        }
        return nums.length + 1;
    }
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 1. 将小于 0 的元素变成正数
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {nums[i] = n + 1;}
        }

        // 2. 将索引为 nums[i] 的元素设置为负数
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 3. 找到第一个大于 0 的元素，返回这个元素对应的下标 i 再加 1
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {return i + 1;}
        }

        return n + 1;
    }

}
